package calcsdk.nw;

import calcsdk.Calcsdk;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author Develop
 */
public class Matrix implements Runnable, Cloneable {

    public float[][] mas = null;
    public float[][] masBackup=null;
    public byte[][] prevZeroStencil=null, curZeroStencil=null;
    public int[] nameH = null;
    public int[] nameV = null;
    public int[] nameHBackup=null;
    public int[] nameVBackup=null;
    public Matrix parentMatrix = null;
    public int threadStarted = 0, threadFinished = 0, threadError = 0;
    //public List<float[][]> hist = new ArrayList<float[][]>();
    float[] minAI = null;
    float[] minAJ = null;
    public Thread thread;
    private List<Patch> patchs = new ArrayList<Patch>();
    private List<Patch> patchsBackup = new ArrayList<Patch>();
    private int start;
    private Max xmax = null;
    private float patchLen = 0;
    private float patchLenBackup;
    private boolean isThread;
    private Calcsdk core = null;
    private int generation;
    //private Patch loopPatchList[]=null;
    //private float[][] zero = null;
    //public List<float[][]> histI = new ArrayList<float[][]>();
    private int mark=0;
    private int avoidMode=0;//0 - ok, 1 - can't avoid
    //ArrayList<MatrixHolder> matrixHolder=new ArrayList<MatrixHolder>();
    ArrayList<Matrix> delayedMatrices=new ArrayList<Matrix>();
    public boolean isDone=false;
    



    /**
     * конструктор первой матрицы
     * @param arr массив длин дуг
     * @param core главный родительский объект
     */
    public Matrix(float[][] arr, Calcsdk core) {
        this.mas = arr;
        this.core = core;
        nameV = new int[mas.length];
        for (int i = 0; i < mas.length; i++) {
            nameV[i] = i;
        }
        nameH = new int[mas[0].length];
        for (int i = 0; i < mas[0].length; i++) {
            nameH[i] = i;
        }
        generation = 0;
        if (core.endPatch != -1) {
            int i = Util.arraySearch(nameV, core.startPatch);
            int j = Util.arraySearch(nameH, core.endPatch);
            addPatch(i, j);
            if (core.avoidCycles) {
                curZeroStencil=new byte[mas.length][mas.length];
                curZeroStencil[i][j]=1;
            }
            new Matrix(this, new Max(i, j, mas[i][j]), core, false);
        } else {
            init();
        }
    }
    
    /**
     * конструктор матрицы
     * @param matrix родительская матрица
     * @param max самый тяжёлый ноль
     * @param core главный родительский объект
     * @param avoidMode разрешено ли обходить зависания
     */
    public Matrix(Matrix matrix, Max max, Calcsdk core, int avoidMode, boolean delayedStart) {
        this.avoidMode=avoidMode;
        preInint(matrix, max, core, delayedStart);
    }

    /**
     * конструктор матрицы
     * @param matrix родительская матрица
     * @param max самый тяжёлый ноль
     * @param core главный родительский объект
     */
    public Matrix(Matrix matrix, Max max, Calcsdk core, boolean delayedStart) {
        this.avoidMode=matrix.avoidMode;
        preInint(matrix, max, core, delayedStart);
    }
    
    /**
     * Предварительная инициализация параметров
     * @param matrix матрица-родитель
     * @param max самый тяжёлый ноль
     * @param core главный родительский объект
     */
    private void preInint(Matrix matrix, Max max, Calcsdk core, boolean delayedStart) {
        try {
            Matrix t_matrix = (Matrix) matrix.clone();// TODO: зачем?
            this.core = core;
            this.mas = Util.arrayCopy(t_matrix.getMas());
            this.nameH = Arrays.copyOf(t_matrix.nameH, t_matrix.nameH.length);
            this.nameV = Arrays.copyOf(t_matrix.nameV, t_matrix.nameV.length);
            this.patchs = new ArrayList<Patch>(t_matrix.getPatchs());
            //this.hist = new ArrayList<float[][]>(t_matrix.getHist());
            this.xmax = max;
            this.patchLen = new Float(t_matrix.patchLen);
            this.parentMatrix = matrix;
            if (parentMatrix != null) {
                parentMatrix.startThr();
            }
            this.prevZeroStencil=matrix.curZeroStencil;
            //this.avoidMode=matrix.avoidMode;
            if (max != null) {
                generation = matrix.generation + 1;
            } else {
                generation = matrix.generation;
            }
            //String t = "";
            //if (max!=null) t=" max: "+max.maxI+" "+max.maxJ;
            //System.out.println("Self: "+this.toString()+" Parent: "+matrix.toString()+t);
            //if (core.DEBUG) print();
            if (!delayedStart) init();
        } catch (Exception ex) {
            ex.printStackTrace();
            core.onError("preInint "+ex);
        }
    }
    

    /**
     * второй этап инициализации, распределение потоков
     */
    public void init() {
        masBackup=Util.arrayCopy(mas);
        nameHBackup=Arrays.copyOf(nameH, nameH.length);
        nameVBackup=Arrays.copyOf(nameV, nameV.length);
        patchsBackup=new ArrayList<Patch>(patchs);
        patchLenBackup=patchLen;
        //zeroStencil=new boolean[mas.length][mas[0].length];
        core.processedMatrices++;
        if (core.maxGeneration < generation) {
            core.maxGeneration = generation;
        }
        //print();
        //printPatchs();
        //if (xmax!=null) System.out.println(xmax.maxI+" "+xmax.maxJ);
        //System.out.println(printToString(mas));
//        try {
//            //Calcsdk.mx.add((Matrix)this.clone());
//        } catch (Exception ex) {
//            ex.printStackTrace();
//        }

        //core.service.getMaximumPoolSize()-10 core.maximumThreads
        if (core.service.getActiveCount() < core.maximumThreads) {//core.daughterThreadNumb < core.daughterThreadMax
            //thread = new Thread(this);
            //thread.setName("Calc");
            //thread.start();
//            while (core.service.getActiveCount()>core.service.getMaximumPoolSize()-100) {
//                try {
//                    Thread.sleep(1);
//                } catch (InterruptedException ex) {}
//            }
            core.daughterThreadNumb++;
            try {
                core.service.submit(this);
            } catch (Exception ex) {
                core.daughterThreadNumb--;
                //ex.printStackTrace();
                //core.onError(ex.getLocalizedMessage());
                return;
            }
        } else {
            if (core.service.isShutdown()) {
                return;
            }
            this.workWrapper();
        }
    }

    @Override
    protected Object clone() throws CloneNotSupportedException {
        /*Matrix t_matrix = new Matrix();
        t_matrix.setMas(arrayCopy(this.mas));
        t_matrix.setPatchs(this.patchs);
        t_matrix.setHist(this.hist);
        return t_matrix;*/
        return super.clone();
    }

//    public synchronized void randomize(int size) {
//        randomize(size, size, 100);
//    }
//
//    private synchronized void randomize(int size, int max) {
//        randomize(size, size, max);
//    }
//
//    public synchronized void randomize(int sizeI, int sizeJ, int max) {
//        Random rnd = new Random();
//        mas = new float[sizeI][sizeJ];
//        for (int i = 0; i < sizeI; i++) {
//            for (int j = 0; j < sizeJ; j++) {
//                if (i == j) {
//                    mas[i][j] = GC.BLC;
//                } else {
//                    mas[i][j] = rnd.nextInt(max);
//                }
//            }
//        }
//    }
//    private synchronized void print(int i, int j, String comment) {
//        System.out.println("[" + comment + "] " + j + "->" + i);
//        print(mas);
//    }

    /**
     * вывод матрицы весов текущего объекта. для дебага
     */
    private synchronized void print() {
        print(this.mas);
    }

    /**
     * вывод весов двумерной матрицы
     * @param mas матрица весов
     */
    public void print(float[][] mas) {
        //synchronized(mas) {// TODO: убрать
        if (mas == null) {
            System.out.println("Матрица пустая");
            return;
        }

        System.out.print("\n\t");
        for (int i = 0; i < mas[0].length; i++) {
            System.out.print(nameH[i] + "\t");
        }
        System.out.println(" ");

        System.out.print("\t");
        for (int i = 0; i < mas[0].length; i++) {
            System.out.print("__\t");
        }
        System.out.println(" ");

        for (int i = 0; i < mas.length; i++) {
            System.out.print(nameV[i] + "|\t");
            for (int j = 0; j < mas[i].length; j++) {
                System.out.print(mas[i][j] + "\t");
            }
            System.out.println(" ");
        }
        //}
    }

    /**
     * вывод матрицы весов в строку
     * @param mas матрица весов
     * @return результирующая строка
     */
    public String printToString(float mas[][]) {
        if (mas == null) {
            return "Матрица пустая\r\n";
        }
        String res = "\t";
        for (int i = 0; i < mas[0].length; i++) {
            res += nameH[i] + "\t";
        }
        res += "\r\n";

        res += "\t";
        for (int i = 0; i < mas[0].length; i++) {
            res += "__\t";
        }
        res += "\r\n";

        for (int i = 0; i < mas.length; i++) {
            res += nameV[i] + "|\t";
            for (int j = 0; j < mas[i].length; j++) {
                res += mas[i][j] + "\t";
            }
            res += "\r\n";
        }
        return res;
    }

    /**
     * приведение матрицы по минимальному расстоянию
     */
    private void min() {
        for (int i = 0; i < mas.length; i++) {
            minJ(i);
        }
        for (int i = 0; i < mas.length; i++) {
            minI(i);
        }
    }

    /**
     * оценка нулевых элементов, включение в маршрут элементов с наибольшей оценкой
     * @return код ошибки
     */
    public int zero() {//synchronized 
        List<Max> maxs = new ArrayList<Max>();
        float max = Float.NEGATIVE_INFINITY, t_max, t_min_i, t_min_j;
        boolean[] numberRow = new boolean[mas.length];//if row has numbers
        boolean[] numberColumn = new boolean[mas[0].length];//if column has numbers
        boolean find = false;
        for (int i = 0; i < mas.length; i++) {
            for (int j = 0; j < mas[i].length; j++) {
                if (mas[i][j] != mas[i][j]) {
                    continue;
                }
                numberRow[i] = true;
                numberColumn[j] = true;

                if (mas[i][j] == 0) {
                    t_min_i = findMinI(i, j);
                    t_min_j = findMinJ(i, j);
                    if (t_min_i == Float.POSITIVE_INFINITY || t_min_j == Float.POSITIVE_INFINITY) {
                        //System.out.println("only inf on "+i+","+j);
                        //continue;
                    }

                    t_max = t_min_i + t_min_j;
                    if (t_max == max) {
                        find = true;
                        maxs.add(new Max(i, j, t_max));
                    }
                    if (t_max > max) {
                        find = true;
                        max = t_max;
                        maxs.clear();
                        maxs.add(new Max(i, j, t_max));
                        //System.out.println("new max at "+i+" "+j+"("+t_min_i+"+"+t_min_j+"="+t_max+")");
                    }
                    find = true;//TODO: файнд, наверно, уже не нужен
                    //maxs.add(new Max(i, j, t_max));
                }
            }
        }
        
        if (core.DEBUG) print();
        if (!find) {//TODO: сюда, поидее, попадать ваще не должны
            //System.out.println("no NaNs and zeros=====================================================");
            //print();
            return -2;// TODO: ан нет, попадаем. если фиктивные вершины использовать
        }
        
        //записываем true на место максимальных нулей в матрицу трафарета,
        //чтоб при обходе зависаний повторно не попасть в эти нули
        if (core.avoidCycles) {
            curZeroStencil=new byte[mas.length][mas.length];
            for (Iterator<Max> it = maxs.iterator(); it.hasNext();) {
                Max max1 = it.next();
                curZeroStencil[max1.maxI][max1.maxJ]=1;
            }
        }
        //if (core.DEBUG) System.out.println(Util.arrayToString(zeroStencil));
        
        for (int i = 0; i < mas.length; i++) {
            if (!numberRow[i]) {
                if (core.DEBUG) {
                    //print();
                    //printPatchs();
                    System.out.println("NaNs in "+i+" row");
                }
				if (core.avoidCycles) onLoop(nameV[i],0);
                return -3;
            }
        }

        for (int i = 0; i < mas[0].length; i++) {
            if (!numberColumn[i]) {
                if (core.DEBUG) {
                    //print();
                    //printPatchs();
                    System.out.println("NaNs in "+i+" column");
                }
				if (core.avoidCycles) onLoop(nameH[i],1);
                return -3;
            }
        }
        //print();
        
        
        
        for (Iterator<Max> it = maxs.iterator(); it.hasNext();) {
            Max max1 = it.next();
            // TODO: зачем создавать переменную, если она не используется? и дальше аналогично
            Matrix matrix = new Matrix(this, max1, core, false);
        }
        
        
        for (Iterator<Matrix> it = delayedMatrices.iterator(); it.hasNext();) {
            Matrix mtx = it.next();
            mtx.init();
        }
        delayedMatrices.clear();
        
        

        //sorting maxes. bigger - first
//        boolean done = false;
//        while (!done) {
//            done = true;
//            for (int i = 1; i < maxs.size(); i++) {
//                if (maxs.get(i).max > maxs.get(i - 1).max) {
//                    Max t = maxs.get(i);
//                    maxs.set(i, maxs.get(i - 1));
//                    maxs.set(i - 1, t);
//                    done = false;
//                }
//            }
//        }

        //threadStarted=maxs.size();
//        if (maxs.size() > 1) {
        //System.out.println(">1 ============"+maxs.size());
        //print();
        

        

//        } else if (maxs.size() == 1) {
//            //System.out.println("=1 ============"+maxs.size());
//            //print();
//            Matrix matrix = new Matrix(this, maxs.get(0));
//            /*if (check(maxs.get(0).getMaxI(), maxs.get(0).getMaxJ())) {
//            min();
//            zero();
//            }*/
//        }



        while (threadFinished + threadError < threadStarted) {
            try {
                Thread.sleep(1);
            } catch (InterruptedException ex) {
                return -16;
            }
            if (core.service.isShutdown()) {
                return -2;
            }
            //System.out.println("phase 1:   fin: "+threadFinished+"   err: "+threadError+"   max: "+threadStarted);
            //print();
        }

        //if (!core.avoidCycles) {
            return 0;
        //}

        /*if (threadError != 0) {
            boolean checkedI[] = new boolean[mas.length];//mark processed lines
            threadStarted = 0;
            threadFinished = 0;
            threadError = 0;
            for (int i = 0; i < maxs.size(); i++) {
                int maxI = maxs.get(i).maxI;
                if (checkedI[maxI]) {
                    continue;
                }

                checkedI[maxI] = true;
                for (int j = 0; j < mas[0].length; j++) {
                    if (mas[maxI][j] != mas[maxI][j]) {// || checkedJ[j]
                        continue;
                    }
                    //threadStarted++;
                    //System.out.println("try " + maxI + " " + j + " " + mas.toString());
                    //print();
                    Matrix matrix = new Matrix(this, new Max(maxI, j, mas[maxI][j]), core);
                }
            }
        } else {
            return 0;//normal exit
        }
        while (threadFinished + threadError < threadStarted) {
            try {
                Thread.sleep(1);
            } catch (InterruptedException ex) {
                return -16;
            }
            if (core.service.isShutdown()) {
                return -2;
            }
            //System.out.println("phase 2:   fin: "+threadFinished+"   err: "+threadError+"   max: "+threadStarted);
        }

        if (threadError == 0) {
            return 0;
        }*/


        /*if ( patchs.size() < (mas.length-2) ) {
        min();
        zero();
        }*/
        //zero();
        //print();
        //return -1;//no paths
    }

    /**
     * поиск нулей в матрице 2х2
     * @return 
     */
    public int findLastZero() {//synchronized 
//        for (int i = 0; i < mas.length; i++) {
//            for (int j = 0; j < mas[i].length; j++) {
//                if (mas[i][j]==0) {
//                    patchs.add(new Patch(nameV[i], nameH[j]));
//                    patchLen+=Calcsdk.origMas[i][j];
//
//                }
//            }
//        }
        int x, y;
        if (mas[0][0] == 0 && mas[1][1] == 0) {
            if (!addPatch(nameV[0], nameH[0])) return -1;
            x = nameV[0] < 1000 ? nameV[0] : nameV[0] / 1000 - 1;
            y = nameH[0] < 1000 ? nameH[0] : nameH[0] / 1000 - 1;
            patchLen += core.origMas[x][y];

            if (!addPatch(nameV[1], nameH[1])) return -1;
            x = nameV[1] < 1000 ? nameV[1] : nameV[1] / 1000 - 1;
            y = nameH[1] < 1000 ? nameH[1] : nameH[1] / 1000 - 1;
            patchLen += core.origMas[x][y];
        } else if (mas[0][1] == 0 && mas[1][0] == 0) {
            if (!addPatch(nameV[0], nameH[1])) return -1;
            x = nameV[0] < 1000 ? nameV[0] : nameV[0] / 1000 - 1;
            y = nameH[1] < 1000 ? nameH[1] : nameH[1] / 1000 - 1;
            patchLen += core.origMas[x][y];

            if (!addPatch(nameV[1], nameH[0])) return -1;
            x = nameV[1] < 1000 ? nameV[1] : nameV[1] / 1000 - 1;
            y = nameH[0] < 1000 ? nameH[0] : nameH[0] / 1000 - 1;
            patchLen += core.origMas[x][y];
        } else {
            //System.out.println("Path'll be to short");
            return 0;
        }
        return -1;// TODO: 123
    }

    /**
     * блокировка обратного хода
     * @param in_i из
     * @param in_j в
     * @param skip_last пропустить последний элемент (для матриц с фиктивными узлами)
     */
    public void block(int in_i, int in_j, int skip_last) {//synchronized 
//        if (!core.useFictive) {
            //System.out.println(in_i+" "+in_j);
            int i = Util.arraySearch(nameV, nameH[in_j]);
            int j = Util.arraySearch(nameH, nameV[in_i]);
            //System.out.println(i+" "+j);
            if (i != -1 && j != -1) {
                mas[i][j] = Float.NaN;
            }
//        } else {
//            int nh = nameToVertexId(nameH[in_j]), nv = nameToVertexId(nameV[in_i]);
//            //System.out.print("Block: "+in_i+" "+in_j+" ("+nv+" "+nh+")");
//            //print();
//            for (int i = 0; i < mas.length - skip_last; i++) {
//                if (nameToVertexId(nameV[i]) == nh) {
//                    for (int j = 0; j < mas[0].length - skip_last; j++) {
//                        if (nameToVertexId(nameH[j]) == nv) {
//                            mas[i][j] = Float.NaN;
//                        }
//                    }
//                }
//            }
//            //		//print();
//        }
    }

    
    /**
     * вычёркивание строки и столбца
     * @param i номер строки
     * @param j номер столбца
     * @return код ошибки
     */
    public int check(int i, int j) {//synchronized 
        if (mas[i][j] == Float.NaN) {
            return 0;
        }
        //System.out.println("Before path addition");
        //printPatchs();
        if (!addPatch(nameV[i], nameH[j])) return -1;//patchs.add(new Patch(i, j));
        int x = nameV[i] < 1000 ? nameV[i] : nameV[i] / 1000 - 1;
        int y = nameH[j] < 1000 ? nameH[j] : nameH[j] / 1000 - 1;
        patchLen += core.origMas[x][y];
        //print();
        //System.out.println("After path addition. pathLen="+patchLen);
        //printPatchs();

        //print();
        //System.out.println("Del " + i + " " + j + "   " + nameV[i] + " " + nameH[j]);

        int _i = Util.arraySearch(nameV, nameH[j]);
        int _j = Util.arraySearch(nameH, nameV[i]);
        //System.out.println("_Del "+_j+" "+_i);
        //System.out.println(i+" "+j+"  "+_j+" "+_i);

        boolean fictiveCreated = false;
        if (core.useFictive) {
//            if (core.transit[y] && patchs.size()>2) {
//                Patch prev=patchs.get(patchs.size()-2);
//                int prevFrom=nameToVertexId(prev.getFrom());
//                int prevTo=nameToVertexId(prev.getTo());
//                if (x==prevTo && y==prevFrom) {
//                    int qwe=0;
//                }
//            }
            
            float[][] _mas = mas;//backup
            int[] _nameH = nameH;//backup
            int[] _nameV = nameV;//backup

            //System.out.println(i+"("+nameV[i]+") "+j+"("+nameH[j]+")  "+_i+" "+_j+"   size: "+mas.length);
            //printPatchs();

            if (_i != -1) {
                //print();
                float[] cpyH = Util.arrayGetRow(mas, _i);//j
                float[] cpyV = Util.arrayGetColumn(mas, j);//_i
                boolean stop = Util.arrayAllNanExceptI(cpyH, j) || Util.arrayAllNanExceptI(cpyV, i);

                int name = nameH[j];
                name = name < 1000 ? (name + 1) * 1000 : name + 1;
                if (name > 1000 && name % 1000 >= core.nodMax[nameToVertexId(name)]) {
                    stop = true;
                }

                if (!stop) {
                    //print();
                    mas = Util.arrayAddRowColumn(mas, cpyH, cpyV);
                    nameH = Util.arrayAddElem(nameH, name);
                    nameV = Util.arrayAddElem(nameV, name);
                    //if (_j != -1) {
                    block(i, j, 1);//block(_i, _j, 1);//
                    //}
                    nameH = Util.arrayDeleteI(nameH, j);
                    nameV = Util.arrayDeleteI(nameV, i);
                    mas = Util.arrayDeleteIJ(mas, i, j);
                    //print();
                    //System.out.println("make fictive");
                    //fictiveCreated=true;
                    if (core.DEBUG) print();
                    
                    delayedMatrices.add(new Matrix(this, null, core, true));
                    //new Matrix(this, null, core, false);
                }
            }

            if (_j != -1) {
                //print();
                float[] cpyH = Util.arrayGetRow(_mas, i);
                float[] cpyV = Util.arrayGetColumn(_mas, _j);
                boolean stop = Util.arrayAllNanExceptI(cpyH, j) || Util.arrayAllNanExceptI(cpyV, i);

                int name = _nameV[i];
                name = name < 1000 ? (name + 1) * 1000 : name + 1;
                if (name > 1000 && name % 1000 >= core.nodMax[nameToVertexId(name)]) {
                    stop = true;
                }

                if (!stop) {
                    mas = Util.arrayAddRowColumn(_mas, cpyH, cpyV);
                    nameH = Util.arrayAddElem(_nameH, name);
                    nameV = Util.arrayAddElem(_nameV, name);
                    //if (_i != -1) {
                    block(i, j, 1);//block(_i, _j, 1);
                    //}
                    nameH = Util.arrayDeleteI(nameH, j);
                    nameV = Util.arrayDeleteI(nameV, i);
                    mas = Util.arrayDeleteIJ(mas, i, j);
                    //print();
                    //System.out.println("\n");
                    //System.out.println("make fictive");
                    //fictiveCreated=true;
                    if (core.DEBUG) print();
                    
                    delayedMatrices.add(new Matrix(this, null, core, true));
                    //new Matrix(this, null, core, false);
                }
            }

            mas = _mas;//restore
            nameH = _nameH;//restore
            nameV = _nameV;//restore
            //print();
            //System.out.println("\n");
        }

        //if (fictiveCreated) return false;

        //if (_j==i) {System.out.println("error "+i+"("+nameV[i]+") "+j+"("+nameH[j]+")  "+_j+" "+_i);parentMatrix.print();}
        //if (_j>i) _j--;
        //if (_i>j) _i--;
        //if (_i != -1 && _j != -1) {
        block(i, j, 0);//block(_i, _j, 0);//
        //}
        nameH = Util.arrayDeleteI(nameH, j);
        nameV = Util.arrayDeleteI(nameV, i);
        mas = Util.arrayDeleteIJ(mas, i, j);
        //System.out.println("continue normal, "+i+" "+j+" deleted");

        //nanI(i);
        //nanJ(j);


        if (mas.length == 2) {//if (patchs.size()==mas.length-2) {
            min();
            if (findLastZero()==-1) return 0;// System.out.println("findLastZero"); print();
            return 0;
        }
        //if (patchs.size() == mas.length) {
        //return true;
        //}
        //System.out.println("the hell are we doing here? "+i+" "+j);
        return 1;
    }

    /**
     * поиск в строке stI минимального j-элемента, пропуская stJ'й элемент
     * @param stI i
     * @param stJ j
     * @return минимальный элемент
     */
    public float findMinJ(int stI, int stJ) {//synchronized 
        float min = Float.POSITIVE_INFINITY;
        //int count=0;
        // TODO: разделить на 2 ФОРа
        for (int j = 0; j < mas[stI].length; j++) {
            if (mas[stI][j] == Float.NaN || j == stJ) {
                continue;//changed here
            }
            if (mas[stI][j] < min /*&& j != stJ && mas[stJ][j]!=0*/) {
                min = mas[stI][j];
            }
        }
        return min;
    }

    /**
     * поиск в столбце stJ минимального i-элемента, пропуская stI'й элемент
     * @param stI i
     * @param stJ j
     * @return минимальный элемент
     */
    public float findMinI(int stI, int stJ) {//synchronized 
        float min = Float.POSITIVE_INFINITY;
        //int count=0;
        // TODO: разделить на 2 ФОРа
        for (int i = 0; i < mas.length; i++) {
            //System.out.println("findMinI "+i+" "+stI+" "+mas[i][stI]);
            if (mas[i][stJ] == Float.NaN || i == stI) {
                continue;//changed here
            }
            if (mas[i][stJ] < min /*&& i != stI && mas[i][stI]!=0*/) {
                min = mas[i][stJ];
            }
        }
        return min;
    }

//    public void nanJ(int stJ) {//synchronized 
//        for (int j = 0; j < mas[stJ].length; j++) {
//            mas[j][stJ] = Float.NaN;//changed here
//        }
//    }

//    public void nanI(int stI) {//synchronized 
//        for (int i = 0; i < mas.length; i++) {
//            mas[stI][i] = Float.NaN;//changed here
//        }
//    }

    /**
     * находит минимальный элемент в столбце и вычитает его из всех элементов этого столбца
     * @param stJ индекс столбца
     * @return минимальный элемент
     */
    public float minJ(int stJ) {//synchronized 
        float min = Float.POSITIVE_INFINITY;
        for (int j = 0; j < mas[stJ].length; j++) {
            if (mas[stJ][j] < min) {
                min = mas[stJ][j];
            }
        }
        if (min == Float.POSITIVE_INFINITY) {
            return min;
        }
        for (int j = 0; j < mas[stJ].length; j++) {
            mas[stJ][j] -= min;
        }
        return min;
    }

    /**
     * находит минимальный элемент в строке и вычитает его из всех элементов этой строки
     * @param stI индекс строки
     * @return минимальный элемент
     */
    public float minI(int stI) {//synchronized 
        float min = Float.POSITIVE_INFINITY;
        for (int i = 0; i < mas.length; i++) {
            if (mas[i][stI] < min) {
                min = mas[i][stI];
            }
        }
        if (min == Float.POSITIVE_INFINITY) {
            return min;
        }
        for (int i = 0; i < mas.length; i++) {
            mas[i][stI] -= min;
        }
        return min;
    }

    /**
     * главный метод потока
     */
    @Override
    public void run() {
        workWrapper();
        core.daughterThreadNumb--;
    }
    
    /**
     * обёртка для главного вычислительного метода. на всякий случай
     */
    private void workWrapper() {
        work();
//        for (int i=0;i<matrixHolder.size();i++) {
//            mas=matrixHolder.get(i).mas;
//            nameH=matrixHolder.get(i).nameH;
//            nameV=matrixHolder.get(i).nameV;
//            Matrix matrix = new Matrix(this, null, core);
//        }
        
        for (Iterator<Matrix> it = delayedMatrices.iterator(); it.hasNext();) {
            Matrix mtx = it.next();
            mtx.init();
        }
        delayedMatrices.clear();
        while (threadFinished + threadError < threadStarted) {
            try {
                Thread.sleep(1);
            } catch (InterruptedException ex) {
                return;
            }
            if (core.service.isShutdown()) {
                return;
            }
        }
        
        isDone=true;
        
        if (parentMatrix != null) {
            parentMatrix.finThr(true);//parentMatrix.threadFinished++;//path OK - normal
        }
    }

    /**
     * главный вычислительный метод
     */
    private void work() {
        //System.out.println("\n\n\nnew mtx");// with maxI="+xmax.getMaxI()+", maxJ="+xmax.getMaxJ()
        int t;
        int res = 0;

        if (xmax != null) {
            res = check(xmax.getMaxI(), xmax.getMaxJ());
            if (res==-1) return;
        }

        if (patchLen > core.shortestPathLen) {
            //if (parentMatrix != null) {
            //    parentMatrix.finThr(true);//parentMatrix.threadFinished++;//path too long - normal
            //}
            return;
        }
        t = tryBuildPatch();
        if (t < 0) {
            if (t == -2) {
                //if (parentMatrix != null) {
                //    parentMatrix.finThr(false);//parentMatrix.threadError++;//short cycle - error
                //}
                if (core.DEBUG) {
                    System.out.print("Short cycle:");
                    print();
                    printPatchs();
                }
                if (core.matrixWriter != null) {
                    core.matrixWriter.add(printToString(mas) + buildPatch() + " " + core.elapsedTime() + "\r\n\r\n");
                }
                return;
            } //else - some other error
        }

        if (xmax != null) {
            if (res==0) {//no more patches
                //print();
                if (t >= 0) {
                    //if (parentMatrix != null) {
                    //    parentMatrix.finThr(true);//parentMatrix.threadFinished++;//path OK - normal
                    //}
                }// else if (parentMatrix != null) {
                //    parentMatrix.finThr(false);//parentMatrix.threadError++;
                //}
                //printPatchs();
                return;
            }
        }


        min();

        t = zero();
        if (t == -16) {
            return; //interrupted
        }
        if (t == -1) {//daughter matrixes failed  (-2 if no zeros, -3 if NaN line)
            //if (parentMatrix != null) {
            //    parentMatrix.finThr(false);//parentMatrix.threadError++;
            //}
            return;
        }

        //if (parentMatrix != null) {
        //    parentMatrix.finThr(true);//parentMatrix.threadFinished++;//no zeroes - normal... or may be not
        //}

    }

    /**
     * увеличение счётчика запущенных потоков
     */
    public synchronized void startThr() {
        threadStarted++;
    }

    /**
     * уменьшение счётчика запущенных потоков
     * @param ok удачно/неудачно
     */
    public synchronized void finThr(boolean ok) {
        if (ok) {
            threadFinished++;
        } else {
            threadError++;
        }
    }

//    public synchronized int getStart() {
//        return start;
//    }
//
//    public synchronized void setStart(int start) {
//        this.start = start;
//    }

    /**
     * возвращает матрицу весов
     * @return матрицу весов
     */
    public synchronized float[][] getMas() {
        return mas;
    }

//    public synchronized void setMas(float[][] mas) {
//        this.mas = mas;
//    }

    /**
     * возвращает список частей пути
     * @return список частей пути
     */
    public synchronized List<Patch> getPatchs() {
        return patchs;
    }

//    public synchronized void setPatchs(List<Patch> patchs) {
//        this.patchs = patchs;
//    }

    /**
     * попытка сформировать путь из найденныйх частей
     * @return код ошибки
     */
    public int tryBuildPatch() {//synchronized
        if (patchs.isEmpty()) return -3;
        int width = core.origMas.length;
        int startVtx=patchs.get(0).getFrom();
        //int cur = startVtx;//core.startPatch;
        int testLen = 0;//TODO: должно совпадать с patchLen, проверить
        int pt = 0;
        boolean checked[] = new boolean[width];
        boolean patchChecked[] = new boolean[patchs.size()];
        if (core.DEBUG) printPatchs();
        
        while (true) {
            LinkedList<Integer> path = new LinkedList<Integer>();//int path[] = new int[width];
            for (int i=0;i<patchChecked.length;i++)
                if (!patchChecked[i]) {path.add(patchs.get(i).getFrom()); break;}

            if (path.isEmpty()) return -3;//all done

            for (Iterator<Patch> it = patchs.iterator(); it.hasNext();) {
                Patch patch = it.next();

                boolean foundNext=false;
                int patchID=0;
                for (Iterator<Patch> it1 = patchs.iterator(); it1.hasNext();) {
                    Patch patch1 = it1.next();
                    if (patchChecked[patchID]) {patchID++; continue;}

                    if (patch1.getFrom() == path.getLast()) {
                        foundNext=true;
                        patchChecked[patchID]=true;
                        int vtxId=nameToVertexId(path.getLast());
                        if (!checked[vtxId]) {
                            pt++;
                        }
                        checked[vtxId] = true;
                        if (pt > width) {
                            return -1;
                        }
                        //path.add(vtxId);//path[pt - 1] = cur;
    //                    int i = patch1.getFrom(), j = patch1.getTo();
    //                    int x = i < 1000 ? i : i / 1000 - 1;
    //                    int y = j < 1000 ? j : j / 1000 - 1;
    //                    testLen += core.origMas[x][y];
                        //cur = patch1.getTo();
                        path.add(patch1.getTo());
                    } else
                    if (patch1.getTo() == path.getFirst()) {
                        foundNext=true;
                        patchChecked[patchID]=true;
                        int vtxId=nameToVertexId(patch1.getFrom());
                        if (!checked[vtxId]) {
                            pt++;
                        }
                        checked[vtxId] = true;
                        path.addFirst(patch1.getFrom());
                    }

                    if (path.getFirst() == path.getLast() && pt != 0) {//nameToVertexId(cur)
                        if (pt == width) {//i==checked.length
                            if (patchLen < core.shortestPathLen) {
                                if (core.DEBUG) {
                                    System.out.println("NEW SHORTEST PATH (" + patchLen + ") ===============================================");
                                }
                                if (core.pathWriter != null) {
                                    core.pathWriter.add("КРАТЧАЙШИЙ ПУТЬ (длина: " + patchLen + ")\r\n");
                                }
                                core.shortestPathLen = patchLen;
                                core.path.clear();
                            }
							int t[]=Util.buildIntArray(path);
							nameToVertexId(t);
                            core.pathAdd(t, this);
                            return 1;//testLen;
                        } else if (!core.useFictive || path.getFirst() == path.getLast())  {
                            return -2;
                        }
                    }

                    patchID++;
                }
                
                if (!foundNext) break;
            }

            int [] t=Util.buildIntArray(path);
            if (core.DEBUG) Util.arrayPrint(t);
            blockCycles(t);
        }
    }

    /**
     * строит путь и выводит его в строку
     * @return строку с путём
     */
    public String buildPatch() {//synchronized 
        int cur = core.startPatch;
        String ret = "[" + patchLen + ": " + cur;
        int pt = 0;
        for (Iterator<Patch> it = patchs.iterator(); it.hasNext();) {
            Patch patch = it.next();
            for (Iterator<Patch> it1 = patchs.iterator(); it1.hasNext();) {
                Patch patch1 = it1.next();

                if (patch1.getFrom() == cur) {
                    if (++pt > core.origMas.length) {
                        break;
                    }
                    ret += "->" + patch1.getTo();
                    cur = patch1.getTo();
                }
            }
        }
        return ret + "]";
    }
    
    /**
     * вывод текущих частей в строку
     * @param addName константа. которая будет добавлена к именам
     * @return строку со списком частей пути
     */
    public String patchesToString(int addName) {
        String ret = "[";
        for (Iterator<Patch> it = patchs.iterator(); it.hasNext();) {
            Patch patch = it.next();
            ret += (patch.getFrom()+addName) + "->" + (patch.getTo()+addName) + "; ";
        }
        ret += "]";
        return ret;
    }
    /**
     * вывод текущих частей в строку
     * @return строку со списком частей пути
     */
    public String patchesToString() {
        return patchesToString(0);
    }

    /**
     * вывод текущих чатей пути. для отладки
     */
    public void printPatchs() {//synchronized 
        System.out.println(buildPatch());

        String ret = "![" + patchLen + ": ";
        for (Iterator<Patch> it = patchs.iterator(); it.hasNext();) {
            Patch patch = it.next();
            ret += patch.getFrom() + "->" + patch.getTo() + "; ";
        }
        ret += "]\r\n";
        System.out.println(ret);
    }

    /*
    public synchronized List<float[][]> getHist() {
    return hist;
    }
    
    public synchronized void setHist(List<float[][]> hist) {
    this.hist = hist;
    }*/
//    public float getPatchLen() {
//        return patchLen;
//    }
//
//    public void setPatchLen(float patchLen) {
//        this.patchLen = patchLen;
//    }

    /**
     * переводи имя вершины в её идентификатор (для фиктивных верщин)
     * @param name имя вершины
     * @return идентификатор вершины
     */
    public int nameToVertexId(int name) {
        return name < 1000 ? name : name / 1000 - 1;
    }
    /**
     * переводит массив имён вершин в массив идентификаторов вершин
     * @param name массив имён вершин
     */
	public void nameToVertexId(int[] name) {
        for (int i=0;i<name.length;i++) name[i]=nameToVertexId(name[i]);
    }
    public List<Patch> nameToVertexId(List<Patch> arr) {
        List<Patch> ret=new ArrayList<Patch>();
        for (Iterator<Patch> it = arr.iterator(); it.hasNext();) {
            Patch patch = it.next();
            ret.add(
                    new Patch(nameToVertexId(patch.getFrom()),
                              nameToVertexId(patch.getTo())
                            ));
        }
        return ret;
    }
    
    /**
     * добавление части пути
     * @param i из
     * @param j в
     * @return true
     */
    public boolean addPatch(int i, int j) {
//        int from,to,blockFrom=-1;
//        for (Iterator<Patch> it = patchs.iterator(); it.hasNext();) {
//            Patch cur = it.next();
//            from=nameToVertexId(cur.getFrom());
//            to=nameToVertexId(cur.getTo());
//            if (nameToVertexId(i)==from && nameToVertexId(j)==to)
//                return false;
//            if (i==cur.getTo()) blockFrom=cur.getFrom();
//        }
//        if (blockFrom!=-1) {
//            from=Util.arraySearch(nameV, blockFrom);
//            to=Util.arraySearch(nameH, j);
//            if (from!=-1 && to!=-1)
//                mas[from][to]=Float.NaN;
//        }
        patchs.add(new Patch(i, j));
        return true;
    }
    
    /**
     * блокировка циклов
     * @param path текущий путь
     */
    public void blockCycles(int path[]) {
        int n=path.length;
        int cur;
        int lastFrom=Util.arraySearch(nameV, path[n-1]);
        int lastTo=Util.arraySearch(nameH, path[n-1]);
        if (lastFrom==-1 && lastTo==-1) return;
        
        for (int i=0;i<n-2;i++) {
            if (lastTo!=-1) {
                cur=Util.arraySearch(nameV, path[i]);
                if (cur!=-1) {
                    mas[cur][lastTo]=Float.NaN;
                    if (core.DEBUG) System.out.println("blocking "+cur+" "+lastTo+" ("+i+" "+path[n-1]+")");
                }
            }
            if (lastFrom!=-1) {
                cur=Util.arraySearch(nameH, path[i]);
                if (cur!=-1) {
                    mas[lastFrom][cur]=Float.NaN;
                    if (core.DEBUG) System.out.println("blocking "+lastFrom+" "+cur+" ("+path[n-1]+" "+i+")");
                }
            }
        }
    }
	
//	public boolean haveBlockedVertex(int vertex) {
//		if (xmax==null) return false;
//        //int j=nameHBackup[xmax.maxJ];
//		//if (core.origMas[vertex][xmax.maxJ]==core.origMas[vertex][xmax.maxJ]) return true;
//        if (vertex==nameHBackup[xmax.maxJ]) return true;
//		return false;
//	}
    
    /**
     * обход зависания путём добавления другого пути (из i в j)
     * @param i из
     * @param j в
     * @return 0
     */
    public int avoidPathTo(int i, int j) {
        //if (mark>0)
        //    return;//System.out.println("MARK "+mark);
        //if (masBackup[i][j]!=masBackup[i][j])
        //    System.out.println("NaN cell");
        
//        if (avoidMode!=0) {// || (parentMatrix!=null && parentMatrix.avoidMode!=0)
//            Matrix cur=this;
//            while (cur.avoidMode!=0) {
//                cur=cur.parentMatrix;
//            }
//            cur.avoidMode=2;
//            return -1;
//        }
        
        float[][] _mas = mas;//local backup
        int[] _nameH = nameH;
        int[] _nameV = nameV;
        List _patchs=patchs;
        float _patchLen=patchLen;

        mas=masBackup;
        nameH=nameHBackup;
        nameV=nameVBackup;
        patchs=patchsBackup;
        patchLen=patchLenBackup;

//                if (parentMatrix.zeroStencil[row][j]) {
//                    print();
//                    int qwe=0;
//                }

        if (core.DEBUG) System.out.println("corrected cut: "+i+" "+j+"("+nameVBackup[i]+" "+nameHBackup[j]+") - "+masBackup[i][j]);
        //avoidMode=1;
        Matrix mtx=new Matrix(this, new Max(i,j,masBackup[i][j]), core, 1, false);

        mas = _mas;//restore
        nameH = _nameH;
        nameV = _nameV;
        patchs=_patchs;
        patchLen=_patchLen;
        
        //if (avoidMode==2)
        //    return 1;
        
        return 0;
        
//        mas = Util.arrayCopy(masBackup);
//        nameH = Arrays.copyOf(nameHBackup, nameHBackup.length);
//        nameV = Arrays.copyOf(nameVBackup, nameVBackup.length);
//        patchs = new ArrayList<Patch>(patchsBackup);
//        xmax = new Max(i,j,masBackup[i][j]);
//        patchLen = new Float(patchLenBackup);
//        threadFinished=0;
//        threadError=0;
//        threadStarted=0;
//        mark++;
//        workWrapper();//init();
    }
    
    /**
     * попытка обхода зависания
     * @param vertex зависшая вершина
     * @param orient 0 - если из вершины нет выходов, 1 - если в вершину нет входов
     * @return если удачно, указатель на матрицу, мз которой был начат обход, иначе - null
     */
    public Matrix tryToAvoid(int vertex, int orient) {
        boolean checkedSmth=false;
        
        if (prevZeroStencil!=null) {
            if (prevZeroStencil.length!=masBackup.length)
                return null;//этого, поидее, не должно быть. но бывает
        }
        
        if (orient==0) {
            int row=Util.arraySearch(nameVBackup, vertex);
            if (row==-1) {return null;}
            for (int j=0;j<masBackup[0].length;j++) {
                if (prevZeroStencil!=null && prevZeroStencil[row][j]==0)
                if (masBackup[row][j]==masBackup[row][j]) {// && masBackup[row][j]>0    ==masBackup[row][j]
                    if (core.DEBUG) System.out.println("try next "+this.toString());
                    avoidPathTo(row, j);
                    checkedSmth=true;
                }
            }
        } else
        if (orient==1){
            int column=Util.arraySearch(nameHBackup, vertex);
            if (column==-1) {return null;}
            for (int i=0;i<masBackup.length;i++) {
                if (prevZeroStencil!=null && prevZeroStencil[i][column]==0)
                if (masBackup[i][column]==masBackup[i][column]) {// && masBackup[i][column]>0    ==masBackup[row][j]
                    if (core.DEBUG) System.out.println("try next "+this.toString());
                    avoidPathTo(i, column);
                    checkedSmth=true;
                }
            }
        }
        
        
        if (parentMatrix!=null) {
            if (checkedSmth) return this;
            else return parentMatrix.tryToAvoid(vertex, orient);
        } else {
            return null;
        }
    }
	
    /**
     * рекурсивный поиск первого вычёркивания вершины
     * @param vertex зависшая вершина
     * @param orient 0 - если из вершины нет выходов, 1 - если в вершину нет входов
     * @return если удачно, указатель на матрицу, мз которой был начат обход, иначе - null
     */
	public Matrix backToFirstCut(int vertex, int orient) {
        if (xmax==null) return null;
        if (core.DEBUG) System.out.println("checking "+this.toString()+" ("+vertex+" | "+nameVBackup[xmax.maxI]+" "+nameHBackup[xmax.maxJ]+")");
		if (vertex==nameHBackup[xmax.maxJ] && orient==0) {
            return tryToAvoid(vertex,0);//поиск в строке
		} else
        if (vertex==nameVBackup[xmax.maxI] && orient==1) {
            return tryToAvoid(vertex,1);//поиск в столбце
        } else {
			if (parentMatrix!=null)
				return parentMatrix.backToFirstCut(vertex, orient);
            else {
				if (core.DEBUG) System.out.println("null error");
                //System.out.println(Util.arrayToString(masBackup));
                return null;
            }
		}
	}
    
    /**
     * функция. вызываемая при обнаружении зависания
     * @param vertex зависшая вершина
     * @param orient 0 - если из вершины нет выходов, 1 - если в вершину нет входов
     */
    public void onLoop(int vertex, int orient) {
        if (avoidMode!=0) {
            if (core.DEBUG) System.out.println("cancel avoid");
            return;
        }
        if (core.DEBUG) {
            System.out.println("new avoid "+this.toString());
        } else {
            if (orient==0 && Util.arraySearch(nameH, vertex)!=-1) return;
            if (orient==1 && Util.arraySearch(nameV, vertex)!=-1) return;
        }
//        Matrix cur=this.parentMatrix;
//        while (cur!=null) {
//            if (cur.loopPatchList!=null)
//            if (Patch.isEqual(cur.patchs, cur.loopPatchList)) {
//                if (core.DEBUG) System.out.println("HAVE CHECKED");
//                return;
//            }
//            cur=cur.parentMatrix;
//        }
//        loopPatchList=Patch.copy(patchs);
        Matrix ret=backToFirstCut(vertex, orient);
		
		if (core.DEBUG && ret==null) System.out.println("return error");
        
        String str="Обнаружено зависание:\r\n"+Util.arrayToString(mas, nameH, nameV, 1)+"\r\n";
        str+="Попытка обхода:\r\n"+(ret==null ? "не получилось обойти." : Util.arrayToString(ret.masBackup, ret.nameHBackup, ret.nameVBackup, 1));
        str+="\r\n\r\n\r\n\r\n";
        
        if (core.matrixWriter!=null) {
            core.matrixWriter.add(str);
        }
        
        if (core.core!=null) core.core.bugPatch(nameToVertexId(patchs), nameToVertexId(vertex), str);
    }
}
